#pragma once
#include<iostream>
#include<list>
#include<assert.h>
using namespace std;

namespace dsh
{
    template<class T>
    struct list_node
    {
        list_node(const T& x = T())
            :_data(x)
             ,_next(nullptr)
             ,_prev(nullptr)
        {}

        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;
    };

    template<class T>
    struct __list_iterator
    {
        typedef list_node<T> Node;
        typedef __list_iterator<T> iterator;

        bool operator!=(const iterator& it)
        {
            return it._node != _node;
        }

        T& operator*()
        {
            return _node->_data; 
        }

        iterator operator++()
        {
            _node = _node->_next;
            return *this;
        }

        __list_iterator(Node* node)
            :_node(node)
        {}

        Node* _node;
    };

    template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        typedef __list_iterator<T> iterator;
        list()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }

        iterator insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;

            Node* newnode = new Node(x);

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;

            return iterator(newnode);
        }

        void push_back(const T& x)
        {
            insert(_head, x);
        }

        iterator erase(iterator pos)
        {
            assert(pos != _head);
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            prev->_next = next;
            next->_prev = prev;

            delete cur;

            return iterator(next);
        }

        void pop_back()
        {
            erase(_head->_prev);
        }

    private:
        Node* _head;
    };

    void test_list1()
    {
        list<int> lt;

        cout << "请输入要插入的结点个数：";
        int n = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cout << "请输入第" << i + 1 << "个结点的数据：";
            int m = 0;
            cin >> m;
            lt.push_back(m);
        }
        cout << "输出链表：";
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;

        cout << "请输入要查找的数据："; 
        int a = 0;
        int flag = 0;
        cin >> a;
        n = 0;
        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
            n++;
            if (it._node->_data == a)
            {
                flag = 1;
                cout << "找到了，为第" << n << "个结点" << endl;
                break;
            }
            ++it;
        }
        if (flag == 0)
            cout << "没有找到" << endl;

        cout << "请输入要取第几个结点的数据：";
        cin >> n;
        it = lt.begin();
        for (int i = 0; i < n - 1; i++)
        {
            ++it;
        }
        cout << "该结点的数据为：" << it._node->_data << endl;

    }
}
